from typing import Optional


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    # define currSum := path sum from root to curr node
    # if exists a recorded path sum == currSum-targetSum, then we have a path with targetSum
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        from collections import defaultdict
        pathCount = defaultdict(int)  # records path sums (from root) encountered
        pathCount[0] += 1  # enable zero path to be stored (解决 currSum == targetSum 情况)

        def dfs(node, currSum) -> int:
            res = 0

            if not node: return 0

            currSum += node.val
            if pathCount[currSum-targetSum]:
                res += pathCount[currSum-targetSum]
            
            pathCount[currSum] += 1
            res += dfs(node.left, currSum)
            res += dfs(node.right, currSum)
            pathCount[currSum] -= 1

            return res
        
        return dfs(root, 0)
    
    
    # 另一种写法，参考参考
    def pathSum2(self, root: Optional[TreeNode], targetSum: int) -> int:
        if not root: return 0

        def dfs(root: Optional[TreeNode], targetSum: int) -> int:
            if not root:
                return 0
            
            res = 0
            if root.val == targetSum:
                res += 1
            
            res += dfs(root.left, targetSum-root.val)
            res += dfs(root.right, targetSum-root.val)
            return res
        
        res = dfs(root, targetSum)  # as usual
        res += dfs(root.left, targetSum)   # skip curr node and go to left
        res += dfs(root.right, targetSum)  # skip curr node and go to right
        return res
